Introduction to Numerical Linear Algebra

- If you change A and b a little, will x only change a little? If the answer is guaranteed to be “yes,” we call the problem well-conditioned. If there are small perturbations of A and/or b resulting in large changes in x, we call the problem ill-conditioned. If the problem is ill- conditioned, we can’t hope to compute x accurately, since small changes in A and b will normally be unavoidable, for instance because of rounding. (This is not to say that we can compute nothing about the solution. For instance, we might be able to compute its average, or some other quantity of interest—just as you might be able to predict climate even if you can’t predict weather.) “Well-conditioned” and “ill-conditioned” are not sharply defined qualitative notions. We’ll develop a way of measuring how ill-conditioned a problem is.

- If you perturb each arithmetic operation a little, will the computed approximation to x only change a little? If so, we call the algorithm stable; otherwise we call it unstable. If we want to make absolutely sure that there will be no confusion with the notions of well- conditioned and ill-conditioned, we also say numerically stable or numerically unstable.

How accurate should one hope the computed approximation to be, with small perturbations in the arithmetic operations? The answer is, the computed approximation should be the exact solution to a slightly perturbed problem. That can mean that it is far off, if the original problem is ill-conditioned; small perturbations in the arithmetic should just not be very much more deleterious than small perturbations in the original problem could be.